# install.packages("tidyverse")
# install.packages("timetk")
library(tidyverse)
library(readr) #read_csv()
library(dplyr)
library(glmnet)
library(timetk)
library(rsample)

1) Load Data

# Load data:
df <- read_csv("./data/walmart_features.csv")
head(df)

Data Preprocessing + Sort Values Notes: Date is already in Date format. Here we just are converting store, holiday_flag from numeric/character to categorical type and dropping redundant columns.

print(sapply(df, class)) # view col datatypes
             store               date               year              month               week              is_q4       weekly_sales       holiday_flag 
         "numeric"             "Date"          "numeric"          "numeric"          "numeric"          "logical"          "numeric"        "character" 
       temperature         fuel_price                cpi       unemployment               lag1               lag2               lag4               lag8 
         "numeric"          "numeric"          "numeric"          "numeric"          "numeric"          "numeric"          "numeric"          "numeric" 
               ma4                ma8 store_mean_to_prev   store_sd_to_prev               sin1               cos1               sin2               cos2 
         "numeric"          "numeric"          "numeric"          "numeric"          "numeric"          "numeric"          "numeric"          "numeric" 
    is_holiday_num inter_holiday_lag1 inter_temp_holiday    inter_cpi_unemp 
         "numeric"          "numeric"          "numeric"          "numeric" 
df <- df %>%
  mutate(
    store = as.factor(store),
    holiday_flag = factor(holiday_flag, levels = unique(holiday_flag))
  ) %>%
  arrange(date, store) %>%  # Sort by date, then store, ascending order
  select(-is_holiday_num) # drop col

head(df)
# Checking the data (uncomment to see output if you wish)
print(dim(df))
[1] 6075   27
#table(df$date) # get value_counts per date -> is 45.

There are 45 stores, so this makes sense, that there are 45 entries for each date. Also, each date represents one week.

2) Train/Test split on sorted data:

Here we perform an 80/20 train/test split to hold back data for comparing different models’ performances. This is not a random split, as we need to preserve time ordering here. Also, it is not a 80/20 split on the row indices, since that could cause some stores with the same date to get split up.

# Train/Test Split:
all_dates <- unique(df$date) # already sorted
cutoff_ix <- floor(0.8 * length(all_dates))
cutoff_date <- all_dates[cutoff_ix]
print(cutoff_date)
[1] "2012-04-20"
train_df <- df %>% filter(date <= cutoff_date)
test_df  <- df %>% filter(date >  cutoff_date)

print(dim(train_df))
[1] 4860   27
print(dim(test_df))
[1] 1215   27
cat("train:", format(min(train_df$date), "%Y-%m-%d"), " to ", format(max(train_df$date), "%Y-%m-%d"),"\n")
train: 2010-04-02  to  2012-04-20 
cat("test:", format(min(test_df$date), "%Y-%m-%d"), " to ", format(max(test_df$date), "%Y-%m-%d"),"\n")
test: 2012-04-27  to  2012-10-26 
print(colnames(df))
 [1] "store"              "date"               "year"               "month"              "week"               "is_q4"              "weekly_sales"      
 [8] "holiday_flag"       "temperature"        "fuel_price"         "cpi"                "unemployment"       "lag1"               "lag2"              
[15] "lag4"               "lag8"               "ma4"                "ma8"                "store_mean_to_prev" "store_sd_to_prev"   "sin1"              
[22] "cos1"               "sin2"               "cos2"               "inter_holiday_lag1" "inter_temp_holiday" "inter_cpi_unemp"   

3) Set Up Rolling Time-series cross validation

Because it is important to keep the future in the test, or else the model could cheat and could use info from the future to predict the past (leakage).

# NOTE - ctrl shift c to mass uncomment/comment out

# Attempt 1 - shorter
# cv_folds <- time_series_cv(
#   data = train_df,
#   date_var = Date,
#   cumulative = FALSE, # no growing window (same size folds)
#   initial = "6 months", # length of train window
#   assess = "3 months", # length of validation window
#   skip = "3 months", # jump between folds
#   slice_limit = 5 # num folds max
# )

# Attempt 2-- longer, cumulative windowing
cv_folds <- time_series_cv(
  data = train_df,
  date_var = date,
  cumulative = TRUE, # growing window (same size folds)
  initial = "1 year", # length of train window
  assess = "3 months", # length of validation window
  skip = "3 months", # jump between folds
  slice_limit = 5 # num folds max
)

plot_time_series_cv_plan(cv_folds, .date_var = date, .value = weekly_sales, .interactive=TRUE)

Additional setup: Define Functions for Standardization Normalize weekly sales within each store, so that no one store dominates, and weekly sales are comparable. i.e. (sales_store - mean(sales_store)) / std(sales_store) and can convert back later via (scaled_sales * store_std) + store_mean

##################### Fit Standard Scaler ###########################
# Returns: mean, std for each col to be used for scaling data.
scaler_fit <- function(df, cols_to_standardize) {
  # For each store, compute mean and std of each col to be standardized
  stats <- df %>%
    group_by(store) %>%
    summarise(
      across(
        all_of(cols_to_standardize),
        list(
          mean = ~mean(.x, na.rm = TRUE),
          sd   = ~sd(.x,   na.rm = TRUE)
        )
      ),
      .groups = "drop"
    )
  # Return a list of std, mean for each col:
  list(
    stats = stats,
    cols  = cols_to_standardize
  )
}

###################### Transform using scaler ############################
# Returns: copy of df, with cols scaled using the scaler. 
#          (Replaces the columns, and no extra cols are added.)
scaler_transform <- function(df, scaler, cols = scaler$cols) {
  stats <- scaler$stats
  
  # join stats onto df by store:
  df2 <- df %>% left_join(stats, by = "store") # create new df2
  
  # For each column, transform via (x - mean) / std, using fitted stats:
  for (col in cols) {
    mean_col <- paste0(col, "_mean") # because stats contains cols with these names
    sd_col   <- paste0(col, "_sd")
    
    df2[[col]] <- (df2[[col]] - df2[[mean_col]]) / df2[[sd_col]] # overwrite col
  }
  
  # remove the helper mean/std columns, so no clutter, and return df2:
  df2 %>% select(-ends_with("_mean"), -ends_with("_sd"))
}

####################### Un-standardize a col (e.g. yhat) #############
scaler_inverse_column <- function(df, scaler, col) {
  stats <- scaler$stats
  
  # Keep only stats for this column, store
  stats_small <- stats %>%
    select(
      store,
      paste0(col, "_mean"),
      paste0(col, "_sd")
    )
  
  df2 <- df %>% left_join(stats_small, by = "store")
  
  mean_col <- paste0(col, "_mean")
  sd_col   <- paste0(col, "_sd")
  
  # Undo z-score: x_raw = x_scaled * sd + mean
  df2[[col]] <- df2[[col]] * df2[[sd_col]] + df2[[mean_col]]
  
  # Drop helper stats
  df2 %>% select(-ends_with("_mean"), -ends_with("_sd"))
}

sales_cols_to_standardize <- c(
  "weekly_sales",
  "lag1", "lag2", "lag4", "lag8",
  "ma4", "ma8",
  "store_mean_to_prev", "store_sd_to_prev",
  "inter_holiday_lag1"
)

Additional setup: Define Cross Validation into one re-usable function Rolling Time-series cross validation for hyperparam selection for lasso: Note: cv_folds contains the full train data. And, design_matrix_formula contains the specification for the features we want for this problem. So, it all checks out.

lasso_cv <- function(cv_folds, lambda_grid, design_matrix_formula,
                     cols_to_standardize=sales_cols_to_standardize) {
  n_folds <- length(cv_folds$splits)
  n_lambdas <- length(lambda_grid)
  cv_mses <- numeric(n_lambdas) # keep track of MSE across different lambdas
  lambda_ix <- 1
  
  for (lambda in lambda_grid) {
    fold_mses <- numeric(n_folds) # array for keeping track of mse across folds
    
    for (fold_ix in 1:n_folds) {
      # Get train, valid data for current cv fold:
      fold <- cv_folds$splits[[fold_ix]]
      train_data <- analysis(fold)
      valid_data <- assessment(fold)
      
      # Standardize cols:
      scaler <- scaler_fit(train_data, cols_to_standardize)
      train_scaled <- scaler_transform(train_data, scaler)
      valid_scaled <- scaler_transform(valid_data, scaler)
      
      # Manipulate data into design matrices:
      X_train <- model.matrix(design_matrix_formula, data=train_scaled)
      y_train <- train_scaled$weekly_sales
      X_val <- model.matrix(design_matrix_formula, data=valid_scaled)
      y_val <- valid_scaled$weekly_sales
      
      # Fit LASSO (non-cv version):
      lasso_model <- glmnet(X_train, y_train, alpha=1, lambda=lambda)
      
      # Get val error:
      yhat_val <- predict(lasso_model, newx=X_val, s=lambda)
      fold_mses[fold_ix] <- mean((y_val - yhat_val)^2)
    }
    cv_mses[lambda_ix] <- mean(fold_mses)
    lambda_ix <- lambda_ix + 1
    
  }
  
  best_lambda <- lambda_grid[which.min(cv_mses)]
  cat("best lambda: ", best_lambda, "with min mse ", min(cv_mses), "\n\n")
  
  plot(x=lambda_grid,
       y=cv_mses,
       main = paste0(n_folds, "-Fold Cross-Validation MSE for different Lambdas"),
       xlab = "Lambda",
       ylab = "Mean CV MSE")
  
  best_lambda
  }

4) Baseline LASSO, no lagged information

# Define design matrix for this test.
design_matrix_formula_baseline_lasso <- weekly_sales ~ holiday_flag + temperature + fuel_price + cpi + unemployment + 0 # 0 means no intercept, glmnet will add its own;

# Define lambda search grid--an easy way to get one with good scaling is from glmnet function itself:
scaler <- scaler_fit(train_df, sales_cols_to_standardize)
train_scaled <- scaler_transform(train_df, scaler)
unused_X_all <- model.matrix(design_matrix_formula_baseline_lasso, data=train_scaled)
unused_y_all <- train_scaled$weekly_sales
unused_model <- glmnet(unused_X_all, unused_y_all, alpha=1)
lambda_grid <- unused_model$lambda
lambda_grid
 [1] 0.1321184830 0.1203814411 0.1096870857 0.0999427873 0.0910641455 0.0829742578 0.0756030534 0.0688866865 0.0627669832 0.0571909374 0.0521102521
[12] 0.0474809210 0.0432628468 0.0394194947 0.0359175755 0.0327267570 0.0298194022 0.0271703286 0.0247565915 0.0225572842 0.0205533572 0.0187274536
[23] 0.0170637582 0.0155478610 0.0141666319 0.0129081073 0.0117613867 0.0107165375 0.0097645098 0.0088970577 0.0081066676 0.0073864936 0.0067302979
[34] 0.0061323968 0.0055876115 0.0050912235 0.0046389333 0.0042268232 0.0038513239 0.0035091829 0.0031974368 0.0029133853 0.0026545682 0.0024187436
[45] 0.0022038691 0.0020080835 0.0018296909 0.0016671462 0.0015190415 0.0013840940 0.0012611349 0.0011490992 0.0010470164 0.0009540023 0.0008692514
[56] 0.0007920295 0.0007216678 0.0006575568 0.0005991413 0.0005459152 0.0004974176 0.0004532284

a) cross val to select lambda

best_lambda <- lasso_cv(cv_folds, lambda_grid, design_matrix_formula_baseline_lasso)
best lambda:  0.007386494 with min mse  1.319609 

b) final model with selected lambda

# Fit model with best lambda on full data, get test error:
test_scaled <- scaler_transform(test_df, scaler)
X_test <- model.matrix(design_matrix_formula_baseline_lasso, data=test_scaled)
y_test_unscaled <- test_df$weekly_sales # not scaled

X_train <- model.matrix(design_matrix_formula_baseline_lasso, data=train_scaled)
y_train <- train_scaled$weekly_sales
best_lasso_model <- glmnet(X_train, y_train, alpha=1, lambda=best_lambda)

# Get val error:
yhat_test <- predict(best_lasso_model, newx=X_test, s=best_lambda)

# Un-scale: (need to build a small fake dataframe for this with store id)
pred_df <- test_df %>% 
  select(store) %>%
  mutate(weekly_sales = yhat_test) # note that this does not actually modify test_df
pred_df_unscaled <- scaler_inverse_column(pred_df, scaler, "weekly_sales")
yhat_test_unscaled <- pred_df_unscaled$weekly_sales

mse_test <- mean((y_test_unscaled - yhat_test_unscaled)^2)
cat("Test MSE (unscaled): ", mse_test, "\n\n")
Test MSE (unscaled):  9717192723 
wape_test <- sum(abs(y_test_unscaled - yhat_test_unscaled)) / sum(abs(y_test_unscaled))
cat("Test WAPE:", wape_test, "\n\n")
Test WAPE: 0.06438912 
coef(best_lasso_model)
7 x 1 sparse Matrix of class "dgCMatrix"
                                   s0
(Intercept)              7.055992e-01
holiday_flagNon-Holiday -4.144757e-01
holiday_flagHoliday      4.963938e-14
temperature             -5.327214e-03
fuel_price              -1.905627e-02
cpi                      3.301644e-04
unemployment             .           

5) LASSO WITH time-lagged features

# colnames(train_df)
# Define design matrix for this test.
design_matrix_formula_all_features <- weekly_sales ~ . - store - date + 0 # 0 means no intercept, glmnet will add its own;

# Define lambda search grid--an easy way to get one with good scaling is from glmnet function itself:
scaler <- scaler_fit(train_df, sales_cols_to_standardize)
train_scaled <- scaler_transform(train_df, scaler)
unused_X_all <- model.matrix(design_matrix_formula_all_features, data=train_scaled)
unused_y_all <- train_scaled$weekly_sales
unused_model <- glmnet(unused_X_all, unused_y_all, alpha=1)
lambda_grid <- unused_model$lambda
lambda_grid
 [1] 0.3932540160 0.3583184131 0.3264863928 0.2974822415 0.2710547391 0.2469749831 0.2250344063 0.2050429699 0.1868275175 0.1702302758 0.1551074873
[12] 0.1413281656 0.1287729609 0.1173331260 0.1069095744 0.0974120225 0.0887582069 0.0808731724 0.0736886227 0.0671423285 0.0611775891 0.0557427407
[23] 0.0507907093 0.0462786026 0.0421673391 0.0384213089 0.0350080657 0.0318980457 0.0290643112 0.0264823179 0.0241297018 0.0219860856 0.0200329023
[34] 0.0182532345 0.0166316674 0.0151541560 0.0138079025 0.0125812465 0.0114635632 0.0104451719 0.0095172516 0.0086717652 0.0079013895 0.0071994518
[45] 0.0065598724 0.0059771114 0.0054461213 0.0049623029 0.0045214656 0.0041197910 0.0037538001 0.0034203229 0.0031164708 0.0028396121 0.0025873488
[56] 0.0023574959 0.0021480625 0.0019572345 0.0017833592 0.0016249305 0.0014805761 0.0013490458 0.0012292003 0.0011200015 0.0010205037 0.0009298450
[67] 0.0008472401 0.0007719736 0.0007033936 0.0006409061 0.0005839697 0.0005320915 0.0004848219 0.0004417517 0.0004025077 0.0003667500 0.0003341690

a) cross val to select lambda

best_lambda <- lasso_cv(cv_folds, lambda_grid, design_matrix_formula_all_features)
best lambda:  0.007901389 with min mse  0.6604256 

b) final model with selected lambda

# Fit model with best lambda on full data, get test error:
test_scaled <- scaler_transform(test_df, scaler)
X_test <- model.matrix(design_matrix_formula_all_features, data=test_scaled)
y_test_unscaled <- test_df$weekly_sales # not scaled

X_train <- model.matrix(design_matrix_formula_all_features, data=train_scaled)
y_train <- train_scaled$weekly_sales
best_lasso_model <- glmnet(X_train, y_train, alpha=1, lambda=best_lambda)

# Get val error:
yhat_test <- predict(best_lasso_model, newx=X_test, s=best_lambda)

# Un-scale: (need to build a small fake dataframe for this with store id)
pred_df <- test_df %>% 
  select(store) %>%
  mutate(weekly_sales = yhat_test) # note that this does not actually modify test_df
pred_df_unscaled <- scaler_inverse_column(pred_df, scaler, "weekly_sales")
yhat_test_unscaled <- pred_df_unscaled$weekly_sales

mse_test <- mean((y_test_unscaled - yhat_test_unscaled)^2)
cat("Test MSE (unscaled): ", mse_test, "\n\n")
Test MSE (unscaled):  4664649702 
wape_test <- sum(abs(y_test_unscaled - yhat_test_unscaled)) / sum(abs(y_test_unscaled))
cat("Test WAPE:", wape_test, "\n\n")
Test WAPE: 0.04349279 
coef(best_lasso_model)
26 x 1 sparse Matrix of class "dgCMatrix"
                               s0
(Intercept)         -1.888898e+02
year                 9.312715e-02
month                2.009185e-01
week                 8.134132e-06
is_q4FALSE          -2.730022e-01
is_q4TRUE            .           
holiday_flagHoliday  5.465857e+00
temperature          .           
fuel_price           3.304306e-02
cpi                  .           
unemployment        -2.463699e-03
lag1                 2.520160e-01
lag2                 1.157488e-01
lag4                 2.403907e-01
lag8                 7.038497e-02
ma4                  6.324143e-02
ma8                 -5.589519e-02
store_mean_to_prev   .           
store_sd_to_prev    -7.858224e-02
sin1                 8.055230e-01
cos1                 2.309093e-02
sin2                 2.121380e-01
cos2                 1.207982e-01
inter_holiday_lag1  -1.553990e+00
inter_temp_holiday   2.827708e-03
inter_cpi_unemp      .           

Sort coeffs

coefs <- as.matrix(coef(best_lasso_model))[, 1]
coefs_sorted <- sort(abs(coefs), decreasing = TRUE)

# Print sorted coefficients with signs
coef_df <- data.frame(
  feature = names(coefs_sorted),
  coef = coefs[names(coefs_sorted)]
)
coef_df

Disregard Anything below this, is either previous notes or unfinished plots

First CV param attempt notes: The above serves as a baseline, when using no time-averaging or time-lagged features. It could just predict the mean, not finding a strong signal with the other features. Next, we will need to try incorporating time. In the meantime, some things I will try are changing the folds and lambdas used.

second CV param attempt notes: Second attempt, used 1 year initial, and cumulative folds. Now holidays and temperature matter, which is better than the first attempt, which had 0’s for all features and intercept was the only kept feature. MSE stayed the same.

LASSO - baseline, NO lagged variables.

5) Plots to analyze the results

Lasso Path–shows variables entering and leaving as lambda (regularization) increases. (NOT cross val).

fit_path <- glmnet(X_train, y_train, alpha = 1)  # doesnt take best lambda, fits a bunch of lambdas, no CV
plot(fit_path, xvar = "lambda", label = TRUE)
title("LASSO Coefficient Paths")


# attempting to get a mapping to var names but this doesnt include intercept (TODO)
beta_mat <- as.matrix(fit_path$beta)
#rownames(beta_mat)
variable_map <- data.frame(
  index = seq_len(nrow(beta_mat)),
  variable = rownames(beta_mat)
)

print(variable_map)
 # 1) Extract coefficients for each tested lambda value, and convert datatype to R matrix:
 Beta_lambda <- as.matrix(coef(fit_path, s=fit_path$lambda))
 
 # 2) Even tho I didn't specify intercept, there is a intercept row of 0's. 
#Beta_lambda <- Beta_lambda[-1,, drop=FALSE] # all rows except row 1, all columns; dont change dimensions
 # print(Beta_lambda)
 cat('Beta_lambda shape:', dim(Beta_lambda), '\n') # shape: (p x #lambdas
 
 # 3) Get L0, L1 norms:
 l1_norm = colSums(abs(Beta_lambda)) # sum up each betah_lambda col; colSums computes sum of each column
 l0_norm = colSums(Beta_lambda != 0) # number of nonzero coeffs for each lambda
 # 4) Want the plot's x axis to be increasing model complexity (incr L1 norm to the right)
 incr_order_ixs = order(l1_norm) # returns indices to make it incr order
 l1_norm_ordered = l1_norm[incr_order_ixs]
 l0_norm_ordered = l0_norm[incr_order_ixs]
 Beta_lambda_ordered = Beta_lambda[,incr_order_ixs,drop=FALSE]
 # 5) Plot coeff vs. L1 norm:
 # note: currently, Beta_lambda's columns are for each lambda, but matplot plots columns of y
 #       as separate lines. We want a line for each coeff (p). Beta_lambda is (p x #lambdas).
 #       so, we take the transpose of beta.
 #       also, num rows should match for x (#lambdas x 1) and y (p x #lambdas).
 cat('L1 norm shape:', length(l1_norm_ordered), '\n')
 cat('Beta_lambda shape:', dim(Beta_lambda_ordered), '\n')
 
 matplot(x=l1_norm,  y=t(Beta_lambda),
 type="l",# plot type: line
 lwd=2, # line width
 lty=1, # line type (solid, dashed)
 xlab=expression("L1 Norm (" * "||" * hat(beta[lambda]) * "||"[1] * ")"),
 ylab="Coefficients",
 main="Lasso Path")
 abline(h = 0, col = "black", lwd = 1, lty = 2) # show x axis more easily
LS0tDQp0aXRsZTogIkxhc3NvIC0gV2FsbWFydDogdXBkYXRlZCBkYXRhIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KYGBge3J9DQojIGluc3RhbGwucGFja2FnZXMoInRpZHl2ZXJzZSIpDQojIGluc3RhbGwucGFja2FnZXMoInRpbWV0ayIpDQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkocmVhZHIpICNyZWFkX2NzdigpDQpsaWJyYXJ5KGRwbHlyKQ0KbGlicmFyeShnbG1uZXQpDQpsaWJyYXJ5KHRpbWV0aykNCmxpYnJhcnkocnNhbXBsZSkNCmBgYA0KDQoNCiMjIyAxKSBMb2FkIERhdGENCmBgYHtyfQ0KIyBMb2FkIGRhdGE6DQpkZiA8LSByZWFkX2NzdigiLi9kYXRhL3dhbG1hcnRfZmVhdHVyZXMuY3N2IikNCmhlYWQoZGYpDQpgYGANCg0KKipEYXRhIFByZXByb2Nlc3NpbmcgKyBTb3J0IFZhbHVlcyoqDQpOb3RlczogRGF0ZSBpcyBhbHJlYWR5IGluIERhdGUgZm9ybWF0LiBIZXJlIHdlIGp1c3QgYXJlIGNvbnZlcnRpbmcgc3RvcmUsIGhvbGlkYXlfZmxhZyBmcm9tIG51bWVyaWMvY2hhcmFjdGVyIHRvIGNhdGVnb3JpY2FsIHR5cGUgYW5kIGRyb3BwaW5nIHJlZHVuZGFudCBjb2x1bW5zLg0KYGBge3J9DQpwcmludChzYXBwbHkoZGYsIGNsYXNzKSkgIyB2aWV3IGNvbCBkYXRhdHlwZXMNCg0KZGYgPC0gZGYgJT4lDQogIG11dGF0ZSgNCiAgICBzdG9yZSA9IGFzLmZhY3RvcihzdG9yZSksDQogICAgaG9saWRheV9mbGFnID0gZmFjdG9yKGhvbGlkYXlfZmxhZywgbGV2ZWxzID0gdW5pcXVlKGhvbGlkYXlfZmxhZykpDQogICkgJT4lDQogIGFycmFuZ2UoZGF0ZSwgc3RvcmUpICU+JSAgIyBTb3J0IGJ5IGRhdGUsIHRoZW4gc3RvcmUsIGFzY2VuZGluZyBvcmRlcg0KICBzZWxlY3QoLWlzX2hvbGlkYXlfbnVtKSAjIGRyb3AgY29sDQoNCmhlYWQoZGYpDQpgYGANCg0KYGBge3J9DQojIENoZWNraW5nIHRoZSBkYXRhICh1bmNvbW1lbnQgdG8gc2VlIG91dHB1dCBpZiB5b3Ugd2lzaCkNCnByaW50KGRpbShkZikpDQojdGFibGUoZGYkZGF0ZSkgIyBnZXQgdmFsdWVfY291bnRzIHBlciBkYXRlIC0+IGlzIDQ1Lg0KYGBgDQoqKlRoZXJlIGFyZSA0NSBzdG9yZXMsIHNvIHRoaXMgbWFrZXMgc2Vuc2UsIHRoYXQgdGhlcmUgYXJlIDQ1IGVudHJpZXMgZm9yIGVhY2ggZGF0ZS4gQWxzbywgZWFjaCBkYXRlIHJlcHJlc2VudHMgb25lIHdlZWsuKioNCg0KIyMjIDIpIFRyYWluL1Rlc3Qgc3BsaXQgb24gc29ydGVkIGRhdGE6DQpIZXJlIHdlIHBlcmZvcm0gYW4gODAvMjAgdHJhaW4vdGVzdCBzcGxpdCB0byBob2xkIGJhY2sgZGF0YSBmb3IgY29tcGFyaW5nIGRpZmZlcmVudCBtb2RlbHMnIHBlcmZvcm1hbmNlcy4gVGhpcyBpcyBub3QgYSANCnJhbmRvbSBzcGxpdCwgYXMgd2UgbmVlZCB0byBwcmVzZXJ2ZSB0aW1lIG9yZGVyaW5nIGhlcmUuIEFsc28sIGl0IGlzIG5vdCBhIDgwLzIwIHNwbGl0IG9uIHRoZSByb3cgaW5kaWNlcywgc2luY2UgdGhhdCBjb3VsZA0KY2F1c2Ugc29tZSBzdG9yZXMgd2l0aCB0aGUgc2FtZSBkYXRlIHRvIGdldCBzcGxpdCB1cC4NCmBgYHtyfQ0KIyBUcmFpbi9UZXN0IFNwbGl0Og0KYWxsX2RhdGVzIDwtIHVuaXF1ZShkZiRkYXRlKSAjIGFscmVhZHkgc29ydGVkDQpjdXRvZmZfaXggPC0gZmxvb3IoMC44ICogbGVuZ3RoKGFsbF9kYXRlcykpDQpjdXRvZmZfZGF0ZSA8LSBhbGxfZGF0ZXNbY3V0b2ZmX2l4XQ0KcHJpbnQoY3V0b2ZmX2RhdGUpDQoNCnRyYWluX2RmIDwtIGRmICU+JSBmaWx0ZXIoZGF0ZSA8PSBjdXRvZmZfZGF0ZSkNCnRlc3RfZGYgIDwtIGRmICU+JSBmaWx0ZXIoZGF0ZSA+ICBjdXRvZmZfZGF0ZSkNCg0KcHJpbnQoZGltKHRyYWluX2RmKSkNCnByaW50KGRpbSh0ZXN0X2RmKSkNCmNhdCgidHJhaW46IiwgZm9ybWF0KG1pbih0cmFpbl9kZiRkYXRlKSwgIiVZLSVtLSVkIiksICIgdG8gIiwgZm9ybWF0KG1heCh0cmFpbl9kZiRkYXRlKSwgIiVZLSVtLSVkIiksIlxuIikNCmNhdCgidGVzdDoiLCBmb3JtYXQobWluKHRlc3RfZGYkZGF0ZSksICIlWS0lbS0lZCIpLCAiIHRvICIsIGZvcm1hdChtYXgodGVzdF9kZiRkYXRlKSwgIiVZLSVtLSVkIiksIlxuIikNCnByaW50KGNvbG5hbWVzKGRmKSkNCg0KYGBgDQojIyMgMykgU2V0IFVwIFJvbGxpbmcgVGltZS1zZXJpZXMgY3Jvc3MgdmFsaWRhdGlvbg0KQmVjYXVzZSBpdCBpcyBpbXBvcnRhbnQgdG8ga2VlcCB0aGUgZnV0dXJlIGluIHRoZSB0ZXN0LCBvciBlbHNlIHRoZSBtb2RlbCBjb3VsZCBjaGVhdCBhbmQgY291bGQgdXNlIGluZm8NCmZyb20gdGhlIGZ1dHVyZSB0byBwcmVkaWN0IHRoZSBwYXN0IChsZWFrYWdlKS4NCmBgYHtyfQ0KIyBOT1RFIC0gY3RybCBzaGlmdCBjIHRvIG1hc3MgdW5jb21tZW50L2NvbW1lbnQgb3V0DQoNCiMgQXR0ZW1wdCAxIC0gc2hvcnRlcg0KIyBjdl9mb2xkcyA8LSB0aW1lX3Nlcmllc19jdigNCiMgICBkYXRhID0gdHJhaW5fZGYsDQojICAgZGF0ZV92YXIgPSBEYXRlLA0KIyAgIGN1bXVsYXRpdmUgPSBGQUxTRSwgIyBubyBncm93aW5nIHdpbmRvdyAoc2FtZSBzaXplIGZvbGRzKQ0KIyAgIGluaXRpYWwgPSAiNiBtb250aHMiLCAjIGxlbmd0aCBvZiB0cmFpbiB3aW5kb3cNCiMgICBhc3Nlc3MgPSAiMyBtb250aHMiLCAjIGxlbmd0aCBvZiB2YWxpZGF0aW9uIHdpbmRvdw0KIyAgIHNraXAgPSAiMyBtb250aHMiLCAjIGp1bXAgYmV0d2VlbiBmb2xkcw0KIyAgIHNsaWNlX2xpbWl0ID0gNSAjIG51bSBmb2xkcyBtYXgNCiMgKQ0KDQojIEF0dGVtcHQgMi0tIGxvbmdlciwgY3VtdWxhdGl2ZSB3aW5kb3dpbmcNCmN2X2ZvbGRzIDwtIHRpbWVfc2VyaWVzX2N2KA0KICBkYXRhID0gdHJhaW5fZGYsDQogIGRhdGVfdmFyID0gZGF0ZSwNCiAgY3VtdWxhdGl2ZSA9IFRSVUUsICMgZ3Jvd2luZyB3aW5kb3cgKHNhbWUgc2l6ZSBmb2xkcykNCiAgaW5pdGlhbCA9ICIxIHllYXIiLCAjIGxlbmd0aCBvZiB0cmFpbiB3aW5kb3cNCiAgYXNzZXNzID0gIjMgbW9udGhzIiwgIyBsZW5ndGggb2YgdmFsaWRhdGlvbiB3aW5kb3cNCiAgc2tpcCA9ICIzIG1vbnRocyIsICMganVtcCBiZXR3ZWVuIGZvbGRzDQogIHNsaWNlX2xpbWl0ID0gNSAjIG51bSBmb2xkcyBtYXgNCikNCg0KcGxvdF90aW1lX3Nlcmllc19jdl9wbGFuKGN2X2ZvbGRzLCAuZGF0ZV92YXIgPSBkYXRlLCAudmFsdWUgPSB3ZWVrbHlfc2FsZXMsIC5pbnRlcmFjdGl2ZT1UUlVFKQ0KYGBgDQoNCioqQWRkaXRpb25hbCBzZXR1cDogRGVmaW5lIEZ1bmN0aW9ucyBmb3IgU3RhbmRhcmRpemF0aW9uKioNCk5vcm1hbGl6ZSB3ZWVrbHkgc2FsZXMgd2l0aGluIGVhY2ggc3RvcmUsIHNvIHRoYXQgbm8gb25lIHN0b3JlIGRvbWluYXRlcywgYW5kIHdlZWtseSBzYWxlcyBhcmUgY29tcGFyYWJsZS4NCmkuZS4gKHNhbGVzX3N0b3JlIC0gbWVhbihzYWxlc19zdG9yZSkpIC8gc3RkKHNhbGVzX3N0b3JlKQ0KYW5kIGNhbiBjb252ZXJ0IGJhY2sgbGF0ZXIgdmlhIChzY2FsZWRfc2FsZXMgKiBzdG9yZV9zdGQpICsgc3RvcmVfbWVhbg0KYGBge3J9DQojIyMjIyMjIyMjIyMjIyMjIyMjIyMgRml0IFN0YW5kYXJkIFNjYWxlciAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiMgUmV0dXJuczogbWVhbiwgc3RkIGZvciBlYWNoIGNvbCB0byBiZSB1c2VkIGZvciBzY2FsaW5nIGRhdGEuDQpzY2FsZXJfZml0IDwtIGZ1bmN0aW9uKGRmLCBjb2xzX3RvX3N0YW5kYXJkaXplKSB7DQogICMgRm9yIGVhY2ggc3RvcmUsIGNvbXB1dGUgbWVhbiBhbmQgc3RkIG9mIGVhY2ggY29sIHRvIGJlIHN0YW5kYXJkaXplZA0KICBzdGF0cyA8LSBkZiAlPiUNCiAgICBncm91cF9ieShzdG9yZSkgJT4lDQogICAgc3VtbWFyaXNlKA0KICAgICAgYWNyb3NzKA0KICAgICAgICBhbGxfb2YoY29sc190b19zdGFuZGFyZGl6ZSksDQogICAgICAgIGxpc3QoDQogICAgICAgICAgbWVhbiA9IH5tZWFuKC54LCBuYS5ybSA9IFRSVUUpLA0KICAgICAgICAgIHNkICAgPSB+c2QoLngsICAgbmEucm0gPSBUUlVFKQ0KICAgICAgICApDQogICAgICApLA0KICAgICAgLmdyb3VwcyA9ICJkcm9wIg0KICAgICkNCiAgIyBSZXR1cm4gYSBsaXN0IG9mIHN0ZCwgbWVhbiBmb3IgZWFjaCBjb2w6DQogIGxpc3QoDQogICAgc3RhdHMgPSBzdGF0cywNCiAgICBjb2xzICA9IGNvbHNfdG9fc3RhbmRhcmRpemUNCiAgKQ0KfQ0KDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIFRyYW5zZm9ybSB1c2luZyBzY2FsZXIgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyBSZXR1cm5zOiBjb3B5IG9mIGRmLCB3aXRoIGNvbHMgc2NhbGVkIHVzaW5nIHRoZSBzY2FsZXIuIA0KIyAgICAgICAgICAoUmVwbGFjZXMgdGhlIGNvbHVtbnMsIGFuZCBubyBleHRyYSBjb2xzIGFyZSBhZGRlZC4pDQpzY2FsZXJfdHJhbnNmb3JtIDwtIGZ1bmN0aW9uKGRmLCBzY2FsZXIsIGNvbHMgPSBzY2FsZXIkY29scykgew0KICBzdGF0cyA8LSBzY2FsZXIkc3RhdHMNCiAgDQogICMgam9pbiBzdGF0cyBvbnRvIGRmIGJ5IHN0b3JlOg0KICBkZjIgPC0gZGYgJT4lIGxlZnRfam9pbihzdGF0cywgYnkgPSAic3RvcmUiKSAjIGNyZWF0ZSBuZXcgZGYyDQogIA0KICAjIEZvciBlYWNoIGNvbHVtbiwgdHJhbnNmb3JtIHZpYSAoeCAtIG1lYW4pIC8gc3RkLCB1c2luZyBmaXR0ZWQgc3RhdHM6DQogIGZvciAoY29sIGluIGNvbHMpIHsNCiAgICBtZWFuX2NvbCA8LSBwYXN0ZTAoY29sLCAiX21lYW4iKSAjIGJlY2F1c2Ugc3RhdHMgY29udGFpbnMgY29scyB3aXRoIHRoZXNlIG5hbWVzDQogICAgc2RfY29sICAgPC0gcGFzdGUwKGNvbCwgIl9zZCIpDQogICAgDQogICAgZGYyW1tjb2xdXSA8LSAoZGYyW1tjb2xdXSAtIGRmMltbbWVhbl9jb2xdXSkgLyBkZjJbW3NkX2NvbF1dICMgb3ZlcndyaXRlIGNvbA0KICB9DQogIA0KICAjIHJlbW92ZSB0aGUgaGVscGVyIG1lYW4vc3RkIGNvbHVtbnMsIHNvIG5vIGNsdXR0ZXIsIGFuZCByZXR1cm4gZGYyOg0KICBkZjIgJT4lIHNlbGVjdCgtZW5kc193aXRoKCJfbWVhbiIpLCAtZW5kc193aXRoKCJfc2QiKSkNCn0NCg0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMgVW4tc3RhbmRhcmRpemUgYSBjb2wgKGUuZy4geWhhdCkgIyMjIyMjIyMjIyMjIw0Kc2NhbGVyX2ludmVyc2VfY29sdW1uIDwtIGZ1bmN0aW9uKGRmLCBzY2FsZXIsIGNvbCkgew0KICBzdGF0cyA8LSBzY2FsZXIkc3RhdHMNCiAgDQogICMgS2VlcCBvbmx5IHN0YXRzIGZvciB0aGlzIGNvbHVtbiwgc3RvcmUNCiAgc3RhdHNfc21hbGwgPC0gc3RhdHMgJT4lDQogICAgc2VsZWN0KA0KICAgICAgc3RvcmUsDQogICAgICBwYXN0ZTAoY29sLCAiX21lYW4iKSwNCiAgICAgIHBhc3RlMChjb2wsICJfc2QiKQ0KICAgICkNCiAgDQogIGRmMiA8LSBkZiAlPiUgbGVmdF9qb2luKHN0YXRzX3NtYWxsLCBieSA9ICJzdG9yZSIpDQogIA0KICBtZWFuX2NvbCA8LSBwYXN0ZTAoY29sLCAiX21lYW4iKQ0KICBzZF9jb2wgICA8LSBwYXN0ZTAoY29sLCAiX3NkIikNCiAgDQogICMgVW5kbyB6LXNjb3JlOiB4X3JhdyA9IHhfc2NhbGVkICogc2QgKyBtZWFuDQogIGRmMltbY29sXV0gPC0gZGYyW1tjb2xdXSAqIGRmMltbc2RfY29sXV0gKyBkZjJbW21lYW5fY29sXV0NCiAgDQogICMgRHJvcCBoZWxwZXIgc3RhdHMNCiAgZGYyICU+JSBzZWxlY3QoLWVuZHNfd2l0aCgiX21lYW4iKSwgLWVuZHNfd2l0aCgiX3NkIikpDQp9DQoNCnNhbGVzX2NvbHNfdG9fc3RhbmRhcmRpemUgPC0gYygNCiAgIndlZWtseV9zYWxlcyIsDQogICJsYWcxIiwgImxhZzIiLCAibGFnNCIsICJsYWc4IiwNCiAgIm1hNCIsICJtYTgiLA0KICAic3RvcmVfbWVhbl90b19wcmV2IiwgInN0b3JlX3NkX3RvX3ByZXYiLA0KICAiaW50ZXJfaG9saWRheV9sYWcxIg0KKQ0KYGBgDQoNCioqQWRkaXRpb25hbCBzZXR1cDogRGVmaW5lIENyb3NzIFZhbGlkYXRpb24gaW50byBvbmUgcmUtdXNhYmxlIGZ1bmN0aW9uKioNClJvbGxpbmcgVGltZS1zZXJpZXMgY3Jvc3MgdmFsaWRhdGlvbiBmb3IgaHlwZXJwYXJhbSBzZWxlY3Rpb24gZm9yIGxhc3NvOg0KTm90ZTogY3ZfZm9sZHMgY29udGFpbnMgdGhlIGZ1bGwgdHJhaW4gZGF0YS4gQW5kLCBkZXNpZ25fbWF0cml4X2Zvcm11bGEgY29udGFpbnMgdGhlDQpzcGVjaWZpY2F0aW9uIGZvciB0aGUgZmVhdHVyZXMgd2Ugd2FudCBmb3IgdGhpcyBwcm9ibGVtLiBTbywgaXQgYWxsIGNoZWNrcyBvdXQuDQpgYGB7cn0NCmxhc3NvX2N2IDwtIGZ1bmN0aW9uKGN2X2ZvbGRzLCBsYW1iZGFfZ3JpZCwgZGVzaWduX21hdHJpeF9mb3JtdWxhLA0KICAgICAgICAgICAgICAgICAgICAgY29sc190b19zdGFuZGFyZGl6ZT1zYWxlc19jb2xzX3RvX3N0YW5kYXJkaXplKSB7DQogIG5fZm9sZHMgPC0gbGVuZ3RoKGN2X2ZvbGRzJHNwbGl0cykNCiAgbl9sYW1iZGFzIDwtIGxlbmd0aChsYW1iZGFfZ3JpZCkNCiAgY3ZfbXNlcyA8LSBudW1lcmljKG5fbGFtYmRhcykgIyBrZWVwIHRyYWNrIG9mIE1TRSBhY3Jvc3MgZGlmZmVyZW50IGxhbWJkYXMNCiAgbGFtYmRhX2l4IDwtIDENCiAgDQogIGZvciAobGFtYmRhIGluIGxhbWJkYV9ncmlkKSB7DQogICAgZm9sZF9tc2VzIDwtIG51bWVyaWMobl9mb2xkcykgIyBhcnJheSBmb3Iga2VlcGluZyB0cmFjayBvZiBtc2UgYWNyb3NzIGZvbGRzDQogICAgDQogICAgZm9yIChmb2xkX2l4IGluIDE6bl9mb2xkcykgew0KICAgICAgIyBHZXQgdHJhaW4sIHZhbGlkIGRhdGEgZm9yIGN1cnJlbnQgY3YgZm9sZDoNCiAgICAgIGZvbGQgPC0gY3ZfZm9sZHMkc3BsaXRzW1tmb2xkX2l4XV0NCiAgICAgIHRyYWluX2RhdGEgPC0gYW5hbHlzaXMoZm9sZCkNCiAgICAgIHZhbGlkX2RhdGEgPC0gYXNzZXNzbWVudChmb2xkKQ0KICAgICAgDQogICAgICAjIFN0YW5kYXJkaXplIGNvbHM6DQogICAgICBzY2FsZXIgPC0gc2NhbGVyX2ZpdCh0cmFpbl9kYXRhLCBjb2xzX3RvX3N0YW5kYXJkaXplKQ0KICAgICAgdHJhaW5fc2NhbGVkIDwtIHNjYWxlcl90cmFuc2Zvcm0odHJhaW5fZGF0YSwgc2NhbGVyKQ0KICAgICAgdmFsaWRfc2NhbGVkIDwtIHNjYWxlcl90cmFuc2Zvcm0odmFsaWRfZGF0YSwgc2NhbGVyKQ0KICAgICAgDQogICAgICAjIE1hbmlwdWxhdGUgZGF0YSBpbnRvIGRlc2lnbiBtYXRyaWNlczoNCiAgICAgIFhfdHJhaW4gPC0gbW9kZWwubWF0cml4KGRlc2lnbl9tYXRyaXhfZm9ybXVsYSwgZGF0YT10cmFpbl9zY2FsZWQpDQogICAgICB5X3RyYWluIDwtIHRyYWluX3NjYWxlZCR3ZWVrbHlfc2FsZXMNCiAgICAgIFhfdmFsIDwtIG1vZGVsLm1hdHJpeChkZXNpZ25fbWF0cml4X2Zvcm11bGEsIGRhdGE9dmFsaWRfc2NhbGVkKQ0KICAgICAgeV92YWwgPC0gdmFsaWRfc2NhbGVkJHdlZWtseV9zYWxlcw0KICAgICAgDQogICAgICAjIEZpdCBMQVNTTyAobm9uLWN2IHZlcnNpb24pOg0KICAgICAgbGFzc29fbW9kZWwgPC0gZ2xtbmV0KFhfdHJhaW4sIHlfdHJhaW4sIGFscGhhPTEsIGxhbWJkYT1sYW1iZGEpDQogICAgICANCiAgICAgICMgR2V0IHZhbCBlcnJvcjoNCiAgICAgIHloYXRfdmFsIDwtIHByZWRpY3QobGFzc29fbW9kZWwsIG5ld3g9WF92YWwsIHM9bGFtYmRhKQ0KICAgICAgZm9sZF9tc2VzW2ZvbGRfaXhdIDwtIG1lYW4oKHlfdmFsIC0geWhhdF92YWwpXjIpDQogICAgfQ0KICAgIGN2X21zZXNbbGFtYmRhX2l4XSA8LSBtZWFuKGZvbGRfbXNlcykNCiAgICBsYW1iZGFfaXggPC0gbGFtYmRhX2l4ICsgMQ0KICAgIA0KICB9DQogIA0KICBiZXN0X2xhbWJkYSA8LSBsYW1iZGFfZ3JpZFt3aGljaC5taW4oY3ZfbXNlcyldDQogIGNhdCgiYmVzdCBsYW1iZGE6ICIsIGJlc3RfbGFtYmRhLCAid2l0aCBtaW4gbXNlICIsIG1pbihjdl9tc2VzKSwgIlxuXG4iKQ0KICANCiAgcGxvdCh4PWxhbWJkYV9ncmlkLA0KICAgICAgIHk9Y3ZfbXNlcywNCiAgICAgICBtYWluID0gcGFzdGUwKG5fZm9sZHMsICItRm9sZCBDcm9zcy1WYWxpZGF0aW9uIE1TRSBmb3IgZGlmZmVyZW50IExhbWJkYXMiKSwNCiAgICAgICB4bGFiID0gIkxhbWJkYSIsDQogICAgICAgeWxhYiA9ICJNZWFuIENWIE1TRSIpDQogIA0KICBiZXN0X2xhbWJkYQ0KICB9DQpgYGANCg0KDQojIyMgNCkgQmFzZWxpbmUgTEFTU08sIG5vIGxhZ2dlZCBpbmZvcm1hdGlvbg0KYGBge3J9DQojIERlZmluZSBkZXNpZ24gbWF0cml4IGZvciB0aGlzIHRlc3QuDQpkZXNpZ25fbWF0cml4X2Zvcm11bGFfYmFzZWxpbmVfbGFzc28gPC0gd2Vla2x5X3NhbGVzIH4gaG9saWRheV9mbGFnICsgdGVtcGVyYXR1cmUgKyBmdWVsX3ByaWNlICsgY3BpICsgdW5lbXBsb3ltZW50ICsgMCAjIDAgbWVhbnMgbm8gaW50ZXJjZXB0LCBnbG1uZXQgd2lsbCBhZGQgaXRzIG93bjsNCg0KIyBEZWZpbmUgbGFtYmRhIHNlYXJjaCBncmlkLS1hbiBlYXN5IHdheSB0byBnZXQgb25lIHdpdGggZ29vZCBzY2FsaW5nIGlzIGZyb20gZ2xtbmV0IGZ1bmN0aW9uIGl0c2VsZjoNCnNjYWxlciA8LSBzY2FsZXJfZml0KHRyYWluX2RmLCBzYWxlc19jb2xzX3RvX3N0YW5kYXJkaXplKQ0KdHJhaW5fc2NhbGVkIDwtIHNjYWxlcl90cmFuc2Zvcm0odHJhaW5fZGYsIHNjYWxlcikNCnVudXNlZF9YX2FsbCA8LSBtb2RlbC5tYXRyaXgoZGVzaWduX21hdHJpeF9mb3JtdWxhX2Jhc2VsaW5lX2xhc3NvLCBkYXRhPXRyYWluX3NjYWxlZCkNCnVudXNlZF95X2FsbCA8LSB0cmFpbl9zY2FsZWQkd2Vla2x5X3NhbGVzDQp1bnVzZWRfbW9kZWwgPC0gZ2xtbmV0KHVudXNlZF9YX2FsbCwgdW51c2VkX3lfYWxsLCBhbHBoYT0xKQ0KbGFtYmRhX2dyaWQgPC0gdW51c2VkX21vZGVsJGxhbWJkYQ0KbGFtYmRhX2dyaWQNCmBgYA0KDQojIyMjIGEpIGNyb3NzIHZhbCB0byBzZWxlY3QgbGFtYmRhDQoNCmBgYHtyfQ0KYmVzdF9sYW1iZGEgPC0gbGFzc29fY3YoY3ZfZm9sZHMsIGxhbWJkYV9ncmlkLCBkZXNpZ25fbWF0cml4X2Zvcm11bGFfYmFzZWxpbmVfbGFzc28pDQpgYGANCiMjIyMgYikgZmluYWwgbW9kZWwgd2l0aCBzZWxlY3RlZCBsYW1iZGENCmBgYHtyfQ0KIyBGaXQgbW9kZWwgd2l0aCBiZXN0IGxhbWJkYSBvbiBmdWxsIGRhdGEsIGdldCB0ZXN0IGVycm9yOg0KdGVzdF9zY2FsZWQgPC0gc2NhbGVyX3RyYW5zZm9ybSh0ZXN0X2RmLCBzY2FsZXIpDQpYX3Rlc3QgPC0gbW9kZWwubWF0cml4KGRlc2lnbl9tYXRyaXhfZm9ybXVsYV9iYXNlbGluZV9sYXNzbywgZGF0YT10ZXN0X3NjYWxlZCkNCnlfdGVzdF91bnNjYWxlZCA8LSB0ZXN0X2RmJHdlZWtseV9zYWxlcyAjIG5vdCBzY2FsZWQNCg0KWF90cmFpbiA8LSBtb2RlbC5tYXRyaXgoZGVzaWduX21hdHJpeF9mb3JtdWxhX2Jhc2VsaW5lX2xhc3NvLCBkYXRhPXRyYWluX3NjYWxlZCkNCnlfdHJhaW4gPC0gdHJhaW5fc2NhbGVkJHdlZWtseV9zYWxlcw0KYmVzdF9sYXNzb19tb2RlbCA8LSBnbG1uZXQoWF90cmFpbiwgeV90cmFpbiwgYWxwaGE9MSwgbGFtYmRhPWJlc3RfbGFtYmRhKQ0KDQojIEdldCB2YWwgZXJyb3I6DQp5aGF0X3Rlc3QgPC0gcHJlZGljdChiZXN0X2xhc3NvX21vZGVsLCBuZXd4PVhfdGVzdCwgcz1iZXN0X2xhbWJkYSkNCg0KIyBVbi1zY2FsZTogKG5lZWQgdG8gYnVpbGQgYSBzbWFsbCBmYWtlIGRhdGFmcmFtZSBmb3IgdGhpcyB3aXRoIHN0b3JlIGlkKQ0KcHJlZF9kZiA8LSB0ZXN0X2RmICU+JSANCiAgc2VsZWN0KHN0b3JlKSAlPiUNCiAgbXV0YXRlKHdlZWtseV9zYWxlcyA9IHloYXRfdGVzdCkgIyBub3RlIHRoYXQgdGhpcyBkb2VzIG5vdCBhY3R1YWxseSBtb2RpZnkgdGVzdF9kZg0KcHJlZF9kZl91bnNjYWxlZCA8LSBzY2FsZXJfaW52ZXJzZV9jb2x1bW4ocHJlZF9kZiwgc2NhbGVyLCAid2Vla2x5X3NhbGVzIikNCnloYXRfdGVzdF91bnNjYWxlZCA8LSBwcmVkX2RmX3Vuc2NhbGVkJHdlZWtseV9zYWxlcw0KDQptc2VfdGVzdCA8LSBtZWFuKCh5X3Rlc3RfdW5zY2FsZWQgLSB5aGF0X3Rlc3RfdW5zY2FsZWQpXjIpDQpjYXQoIlRlc3QgTVNFICh1bnNjYWxlZCk6ICIsIG1zZV90ZXN0LCAiXG5cbiIpDQoNCndhcGVfdGVzdCA8LSBzdW0oYWJzKHlfdGVzdF91bnNjYWxlZCAtIHloYXRfdGVzdF91bnNjYWxlZCkpIC8gc3VtKGFicyh5X3Rlc3RfdW5zY2FsZWQpKQ0KY2F0KCJUZXN0IFdBUEU6Iiwgd2FwZV90ZXN0LCAiXG5cbiIpDQoNCmNvZWYoYmVzdF9sYXNzb19tb2RlbCkNCmBgYA0KIyMjIDUpIExBU1NPIFdJVEggdGltZS1sYWdnZWQgZmVhdHVyZXMNCmBgYHtyfQ0KIyBjb2xuYW1lcyh0cmFpbl9kZikNCiMgRGVmaW5lIGRlc2lnbiBtYXRyaXggZm9yIHRoaXMgdGVzdC4NCmRlc2lnbl9tYXRyaXhfZm9ybXVsYV9hbGxfZmVhdHVyZXMgPC0gd2Vla2x5X3NhbGVzIH4gLiAtIHN0b3JlIC0gZGF0ZSArIDAgIyAwIG1lYW5zIG5vIGludGVyY2VwdCwgZ2xtbmV0IHdpbGwgYWRkIGl0cyBvd247DQoNCiMgRGVmaW5lIGxhbWJkYSBzZWFyY2ggZ3JpZC0tYW4gZWFzeSB3YXkgdG8gZ2V0IG9uZSB3aXRoIGdvb2Qgc2NhbGluZyBpcyBmcm9tIGdsbW5ldCBmdW5jdGlvbiBpdHNlbGY6DQpzY2FsZXIgPC0gc2NhbGVyX2ZpdCh0cmFpbl9kZiwgc2FsZXNfY29sc190b19zdGFuZGFyZGl6ZSkNCnRyYWluX3NjYWxlZCA8LSBzY2FsZXJfdHJhbnNmb3JtKHRyYWluX2RmLCBzY2FsZXIpDQp1bnVzZWRfWF9hbGwgPC0gbW9kZWwubWF0cml4KGRlc2lnbl9tYXRyaXhfZm9ybXVsYV9hbGxfZmVhdHVyZXMsIGRhdGE9dHJhaW5fc2NhbGVkKQ0KdW51c2VkX3lfYWxsIDwtIHRyYWluX3NjYWxlZCR3ZWVrbHlfc2FsZXMNCnVudXNlZF9tb2RlbCA8LSBnbG1uZXQodW51c2VkX1hfYWxsLCB1bnVzZWRfeV9hbGwsIGFscGhhPTEpDQpsYW1iZGFfZ3JpZCA8LSB1bnVzZWRfbW9kZWwkbGFtYmRhDQpsYW1iZGFfZ3JpZA0KYGBgDQojIyMjIGEpIGNyb3NzIHZhbCB0byBzZWxlY3QgbGFtYmRhDQpgYGB7cn0NCmJlc3RfbGFtYmRhIDwtIGxhc3NvX2N2KGN2X2ZvbGRzLCBsYW1iZGFfZ3JpZCwgZGVzaWduX21hdHJpeF9mb3JtdWxhX2FsbF9mZWF0dXJlcykNCmBgYA0KDQojIyMjIGIpIGZpbmFsIG1vZGVsIHdpdGggc2VsZWN0ZWQgbGFtYmRhDQpgYGB7cn0NCiMgRml0IG1vZGVsIHdpdGggYmVzdCBsYW1iZGEgb24gZnVsbCBkYXRhLCBnZXQgdGVzdCBlcnJvcjoNCnRlc3Rfc2NhbGVkIDwtIHNjYWxlcl90cmFuc2Zvcm0odGVzdF9kZiwgc2NhbGVyKQ0KWF90ZXN0IDwtIG1vZGVsLm1hdHJpeChkZXNpZ25fbWF0cml4X2Zvcm11bGFfYWxsX2ZlYXR1cmVzLCBkYXRhPXRlc3Rfc2NhbGVkKQ0KeV90ZXN0X3Vuc2NhbGVkIDwtIHRlc3RfZGYkd2Vla2x5X3NhbGVzICMgbm90IHNjYWxlZA0KDQpYX3RyYWluIDwtIG1vZGVsLm1hdHJpeChkZXNpZ25fbWF0cml4X2Zvcm11bGFfYWxsX2ZlYXR1cmVzLCBkYXRhPXRyYWluX3NjYWxlZCkNCnlfdHJhaW4gPC0gdHJhaW5fc2NhbGVkJHdlZWtseV9zYWxlcw0KYmVzdF9sYXNzb19tb2RlbCA8LSBnbG1uZXQoWF90cmFpbiwgeV90cmFpbiwgYWxwaGE9MSwgbGFtYmRhPWJlc3RfbGFtYmRhKQ0KDQojIEdldCB2YWwgZXJyb3I6DQp5aGF0X3Rlc3QgPC0gcHJlZGljdChiZXN0X2xhc3NvX21vZGVsLCBuZXd4PVhfdGVzdCwgcz1iZXN0X2xhbWJkYSkNCg0KIyBVbi1zY2FsZTogKG5lZWQgdG8gYnVpbGQgYSBzbWFsbCBmYWtlIGRhdGFmcmFtZSBmb3IgdGhpcyB3aXRoIHN0b3JlIGlkKQ0KcHJlZF9kZiA8LSB0ZXN0X2RmICU+JSANCiAgc2VsZWN0KHN0b3JlKSAlPiUNCiAgbXV0YXRlKHdlZWtseV9zYWxlcyA9IHloYXRfdGVzdCkgIyBub3RlIHRoYXQgdGhpcyBkb2VzIG5vdCBhY3R1YWxseSBtb2RpZnkgdGVzdF9kZg0KcHJlZF9kZl91bnNjYWxlZCA8LSBzY2FsZXJfaW52ZXJzZV9jb2x1bW4ocHJlZF9kZiwgc2NhbGVyLCAid2Vla2x5X3NhbGVzIikNCnloYXRfdGVzdF91bnNjYWxlZCA8LSBwcmVkX2RmX3Vuc2NhbGVkJHdlZWtseV9zYWxlcw0KDQptc2VfdGVzdCA8LSBtZWFuKCh5X3Rlc3RfdW5zY2FsZWQgLSB5aGF0X3Rlc3RfdW5zY2FsZWQpXjIpDQpjYXQoIlRlc3QgTVNFICh1bnNjYWxlZCk6ICIsIG1zZV90ZXN0LCAiXG5cbiIpDQoNCndhcGVfdGVzdCA8LSBzdW0oYWJzKHlfdGVzdF91bnNjYWxlZCAtIHloYXRfdGVzdF91bnNjYWxlZCkpIC8gc3VtKGFicyh5X3Rlc3RfdW5zY2FsZWQpKQ0KY2F0KCJUZXN0IFdBUEU6Iiwgd2FwZV90ZXN0LCAiXG5cbiIpDQoNCmNvZWYoYmVzdF9sYXNzb19tb2RlbCkNCmBgYA0KKipTb3J0IGNvZWZmcyoqDQpgYGB7cn0NCmNvZWZzIDwtIGFzLm1hdHJpeChjb2VmKGJlc3RfbGFzc29fbW9kZWwpKVssIDFdDQpjb2Vmc19zb3J0ZWQgPC0gc29ydChhYnMoY29lZnMpLCBkZWNyZWFzaW5nID0gVFJVRSkNCg0KIyBQcmludCBzb3J0ZWQgY29lZmZpY2llbnRzIHdpdGggc2lnbnMNCmNvZWZfZGYgPC0gZGF0YS5mcmFtZSgNCiAgZmVhdHVyZSA9IG5hbWVzKGNvZWZzX3NvcnRlZCksDQogIGNvZWYgPSBjb2Vmc1tuYW1lcyhjb2Vmc19zb3J0ZWQpXQ0KKQ0KY29lZl9kZg0KYGBgDQoNCg0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQojIyBEaXNyZWdhcmQgQW55dGhpbmcgYmVsb3cgdGhpcywgaXMgZWl0aGVyIHByZXZpb3VzIG5vdGVzIG9yIHVuZmluaXNoZWQgcGxvdHMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCg0KDQoqKkZpcnN0IENWIHBhcmFtIGF0dGVtcHQgbm90ZXM6KioNClRoZSBhYm92ZSBzZXJ2ZXMgYXMgYSBiYXNlbGluZSwgd2hlbiB1c2luZyBubyB0aW1lLWF2ZXJhZ2luZyBvciB0aW1lLWxhZ2dlZCBmZWF0dXJlcy4gSXQgY291bGQganVzdCBwcmVkaWN0IHRoZSBtZWFuLCBub3QgZmluZGluZyBhIHN0cm9uZyBzaWduYWwgd2l0aCB0aGUgb3RoZXIgZmVhdHVyZXMuIE5leHQsIHdlIHdpbGwgbmVlZCB0byB0cnkgaW5jb3Jwb3JhdGluZyB0aW1lLiBJbiB0aGUgbWVhbnRpbWUsIHNvbWUgdGhpbmdzIEkgd2lsbCB0cnkgYXJlIGNoYW5naW5nIHRoZSBmb2xkcyBhbmQgbGFtYmRhcyB1c2VkLg0KDQoqKnNlY29uZCBDViBwYXJhbSBhdHRlbXB0IG5vdGVzOioqDQpTZWNvbmQgYXR0ZW1wdCwgdXNlZCAxIHllYXIgaW5pdGlhbCwgYW5kIGN1bXVsYXRpdmUgZm9sZHMuIE5vdyBob2xpZGF5cyBhbmQgdGVtcGVyYXR1cmUgbWF0dGVyLCB3aGljaCBpcyBiZXR0ZXIgdGhhbiB0aGUgZmlyc3QgYXR0ZW1wdCwgd2hpY2ggaGFkIDAncyBmb3IgYWxsIGZlYXR1cmVzIGFuZCBpbnRlcmNlcHQgd2FzIHRoZSBvbmx5IGtlcHQgZmVhdHVyZS4gTVNFIHN0YXllZCB0aGUgc2FtZS4NCg0KTEFTU08gLSBiYXNlbGluZSwgTk8gbGFnZ2VkIHZhcmlhYmxlcy4NCg0KIyMjIDUpIFBsb3RzIHRvIGFuYWx5emUgdGhlIHJlc3VsdHMNCioqTGFzc28gUGF0aC0tc2hvd3MgdmFyaWFibGVzIGVudGVyaW5nIGFuZCBsZWF2aW5nIGFzIGxhbWJkYSAocmVndWxhcml6YXRpb24pIGluY3JlYXNlcy4gKE5PVCBjcm9zcyB2YWwpLioqDQpgYGB7cn0NCmZpdF9wYXRoIDwtIGdsbW5ldChYX3RyYWluLCB5X3RyYWluLCBhbHBoYSA9IDEpICAjIGRvZXNudCB0YWtlIGJlc3QgbGFtYmRhLCBmaXRzIGEgYnVuY2ggb2YgbGFtYmRhcywgbm8gQ1YNCnBsb3QoZml0X3BhdGgsIHh2YXIgPSAibGFtYmRhIiwgbGFiZWwgPSBUUlVFKQ0KdGl0bGUoIkxBU1NPIENvZWZmaWNpZW50IFBhdGhzIikNCg0KDQojIGF0dGVtcHRpbmcgdG8gZ2V0IGEgbWFwcGluZyB0byB2YXIgbmFtZXMgYnV0IHRoaXMgZG9lc250IGluY2x1ZGUgaW50ZXJjZXB0IChUT0RPKQ0KYmV0YV9tYXQgPC0gYXMubWF0cml4KGZpdF9wYXRoJGJldGEpDQojcm93bmFtZXMoYmV0YV9tYXQpDQp2YXJpYWJsZV9tYXAgPC0gZGF0YS5mcmFtZSgNCiAgaW5kZXggPSBzZXFfbGVuKG5yb3coYmV0YV9tYXQpKSwNCiAgdmFyaWFibGUgPSByb3duYW1lcyhiZXRhX21hdCkNCikNCg0KcHJpbnQodmFyaWFibGVfbWFwKQ0KYGBgDQpgYGB7cn0NCiAjIDEpIEV4dHJhY3QgY29lZmZpY2llbnRzIGZvciBlYWNoIHRlc3RlZCBsYW1iZGEgdmFsdWUsIGFuZCBjb252ZXJ0IGRhdGF0eXBlIHRvIFIgbWF0cml4Og0KIEJldGFfbGFtYmRhIDwtIGFzLm1hdHJpeChjb2VmKGZpdF9wYXRoLCBzPWZpdF9wYXRoJGxhbWJkYSkpDQogDQogIyAyKSBFdmVuIHRobyBJIGRpZG4ndCBzcGVjaWZ5IGludGVyY2VwdCwgdGhlcmUgaXMgYSBpbnRlcmNlcHQgcm93IG9mIDAncy4gDQojQmV0YV9sYW1iZGEgPC0gQmV0YV9sYW1iZGFbLTEsLCBkcm9wPUZBTFNFXSAjIGFsbCByb3dzIGV4Y2VwdCByb3cgMSwgYWxsIGNvbHVtbnM7IGRvbnQgY2hhbmdlIGRpbWVuc2lvbnMNCiAjIHByaW50KEJldGFfbGFtYmRhKQ0KIGNhdCgnQmV0YV9sYW1iZGEgc2hhcGU6JywgZGltKEJldGFfbGFtYmRhKSwgJ1xuJykgIyBzaGFwZTogKHAgeCAjbGFtYmRhcw0KIA0KICMgMykgR2V0IEwwLCBMMSBub3JtczoNCiBsMV9ub3JtID0gY29sU3VtcyhhYnMoQmV0YV9sYW1iZGEpKSAjIHN1bSB1cCBlYWNoIGJldGFoX2xhbWJkYSBjb2w7IGNvbFN1bXMgY29tcHV0ZXMgc3VtIG9mIGVhY2ggY29sdW1uDQogbDBfbm9ybSA9IGNvbFN1bXMoQmV0YV9sYW1iZGEgIT0gMCkgIyBudW1iZXIgb2Ygbm9uemVybyBjb2VmZnMgZm9yIGVhY2ggbGFtYmRhDQogIyA0KSBXYW50IHRoZSBwbG90J3MgeCBheGlzIHRvIGJlIGluY3JlYXNpbmcgbW9kZWwgY29tcGxleGl0eSAoaW5jciBMMSBub3JtIHRvIHRoZSByaWdodCkNCiBpbmNyX29yZGVyX2l4cyA9IG9yZGVyKGwxX25vcm0pICMgcmV0dXJucyBpbmRpY2VzIHRvIG1ha2UgaXQgaW5jciBvcmRlcg0KIGwxX25vcm1fb3JkZXJlZCA9IGwxX25vcm1baW5jcl9vcmRlcl9peHNdDQogbDBfbm9ybV9vcmRlcmVkID0gbDBfbm9ybVtpbmNyX29yZGVyX2l4c10NCiBCZXRhX2xhbWJkYV9vcmRlcmVkID0gQmV0YV9sYW1iZGFbLGluY3Jfb3JkZXJfaXhzLGRyb3A9RkFMU0VdDQogIyA1KSBQbG90IGNvZWZmIHZzLiBMMSBub3JtOg0KICMgbm90ZTogY3VycmVudGx5LCBCZXRhX2xhbWJkYSdzIGNvbHVtbnMgYXJlIGZvciBlYWNoIGxhbWJkYSwgYnV0IG1hdHBsb3QgcGxvdHMgY29sdW1ucyBvZiB5DQogIyAgICAgICBhcyBzZXBhcmF0ZSBsaW5lcy4gV2Ugd2FudCBhIGxpbmUgZm9yIGVhY2ggY29lZmYgKHApLiBCZXRhX2xhbWJkYSBpcyAocCB4ICNsYW1iZGFzKS4NCiAjICAgICAgIHNvLCB3ZSB0YWtlIHRoZSB0cmFuc3Bvc2Ugb2YgYmV0YS4NCiAjICAgICAgIGFsc28sIG51bSByb3dzIHNob3VsZCBtYXRjaCBmb3IgeCAoI2xhbWJkYXMgeCAxKSBhbmQgeSAocCB4ICNsYW1iZGFzKS4NCiBjYXQoJ0wxIG5vcm0gc2hhcGU6JywgbGVuZ3RoKGwxX25vcm1fb3JkZXJlZCksICdcbicpDQogY2F0KCdCZXRhX2xhbWJkYSBzaGFwZTonLCBkaW0oQmV0YV9sYW1iZGFfb3JkZXJlZCksICdcbicpDQogDQogbWF0cGxvdCh4PWwxX25vcm0sICB5PXQoQmV0YV9sYW1iZGEpLA0KIHR5cGU9ImwiLCMgcGxvdCB0eXBlOiBsaW5lDQogbHdkPTIsICMgbGluZSB3aWR0aA0KIGx0eT0xLCAjIGxpbmUgdHlwZSAoc29saWQsIGRhc2hlZCkNCiB4bGFiPWV4cHJlc3Npb24oIkwxIE5vcm0gKCIgKiAifHwiICogaGF0KGJldGFbbGFtYmRhXSkgKiAifHwiWzFdICogIikiKSwNCiB5bGFiPSJDb2VmZmljaWVudHMiLA0KIG1haW49Ikxhc3NvIFBhdGgiKQ0KIGFibGluZShoID0gMCwgY29sID0gImJsYWNrIiwgbHdkID0gMSwgbHR5ID0gMikgIyBzaG93IHggYXhpcyBtb3JlIGVhc2lseQ0KYGBgDQoNCg==